\begin{frame}
\frametitle{Finite Automata}

\begin{define}[NFA~\cite{Morita2004}, 4FNA~\cite{Giammarresi1997},
2-FA~\cite{Inoue1979}, \cite{Blum:1967:AT:1674645.1675318}, AF, DF, NF,
UF~\cite{Ito1997}] A non-deterministic two-dimensional finite automaton is a 6-tuple
$M~=~(Z, \Sigma, \delta, z_0, z_e, z_r)$, where

\begin{itemize}
	\item Z is a finite set of states
	\item $\Sigma$ is a finite set of input symbols
	\item $z_0$, $z_a$ and $z_r$ is the starting, accepting and rejecting
		state
	\item $\delta: (\text{Z }\backslash \{z_a, z_r\}) \times (\Sigma \cup
		\{\#\}) \rightarrow 2^{Z \times \Delta}$ is the control function, where $\#
		\not\in  \Sigma$ is the boundary symbol and $\Delta = \{L, R, U, D\}$ can be
		thought of as a set of directions
\end{itemize}

\end{define}

\end{frame}

\begin{frame}[allowframebreaks]
\frametitle{Example}

\begin{example}
$M~=~(\{z_0, \ldots, z_9, z_r, z_e\}, \{0,1\}, \delta, z_0, z_e,
z_r)$, $y = \{0, 1\}$

$\delta(z_0, y) = (z_1, r), \delta(z_0, \#) = (z_r, u)$
$\delta(z_1, y) = (z_0, d), \delta(z_1, \#) = (z_2, l)$\\
$\delta(z_2, y) = (z_3, d)$ \\
$\delta(z_3, y) = (z_r, u), \delta(z_3, \#) = (z_4, u)$
$\delta(z_4, y) = (z_5, u), \delta(z_4, 1) = (z_7, r), \delta(z_4, \#) = (z_r,
r)$ 
$\delta(z_5, y) = (z_4, l), \delta(z_5, \#) = (z_r, d)$
$\delta(z_6, y) = (z_7, r), \delta(z_6, \#) = (z_r, d)$ 
$\delta(z_7, y) = (z_6, u), \delta(z_7, \#) = (z_8, l)$ \\ 
$\delta(z_8, y) = (z_9, u)$ \\
$\delta(z_9, y) = (z_r, d), \delta(z_9, \#) = (z_e, d)$ 
\end{example}

\begin{align*}
L = \{p\mid &p\in\Sigma^{**},~l_1(p)~=~l_2(p),~l_1(p)~\%~2~=~1~\wedge \\
  &p(\lfloor{l_1(p)/2\rfloor}~+~1,~\lfloor{l_2(p)/2\rfloor}~+~1)~=~1\}  \\
\end{align*}

$L$ is the language of all quadratic pictures with odd side length and 1 in
its center. \\

\begin{align*}
L(M) &= \{p \in \Sigma^{**}\mid \text{p is accepted by M}\}\\
L(M) &= L
\end{align*}

\end{frame}

\begin{frame}
\frametitle{Closure Properties}

\begin{thm}[Theorem 4.2~\cite{Giammarresi1997}, Theorem
2~\cite{Kari01newresults}, Theorem 4.5,4.6~\cite{Ito1997}] $\mathcal{L}(DFA)\text{,
}\mathcal{L}(NFA)\text{, }\mathcal{L}(UFA)\text{ and }\mathcal{L}(AFA)$ are not
closed under row and column catenation, row and column closure, row
and column cyclic closure and projection.
Moreover $\mathcal{L}(UFA)\text{, }\mathcal{L}(AFA)$ are not closed under complement and
over unary alphabets $\mathcal{L}(NFA)$ is not closed under complementation too.
\end{thm}

\begin{thm}[Theorem 4.3~\cite{Giammarresi1997},
Introduction~\cite{Kari01newresults}, Summary~\cite{Ito1997}] $\mathcal{L}(DFA)\text{,
}\mathcal{L}(NFA)\text{, }\mathcal{L}(UFA)\text{ and }\mathcal{L}(AFA)$ are closed under boolean intersection.
$\mathcal{L}(DFA)\text{, }\mathcal{L}(NFA)\text{ and }\mathcal{L}(AFA)$
are closed under boolean union. Moreover $\mathcal{L}(DFA)$ is closed
under complement.
\end{thm}

\end{frame}

\begin{frame}
\frametitle{Language hierarchy}

\begin{thm}[Theorem 22.2.2~\cite{Morita2004}, Theorem 4.1~\cite{Giammarresi1997}]
$\mathcal{L}(DFA)\subset\mathcal{L}(NFA)$
\end{thm}

\begin{thm}[Theorem 5~\cite{Kari01newresults}]
$\mathcal{L}(DFA)\subset\mathcal{L}(NFA)\subset\mathcal{L}(AFA)$ for picture
languages over an unary alphabet.
\end{thm}

\end{frame}